public class PrimeNumberCalculator {

    /**
     * 方法1：基础判断法（性能较低）
     * 判断单个数字是否为素数
     */
    public static boolean isPrimeBasic(int num) {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;

        // 只需要检查到sqrt(num)
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 方法2：埃拉托斯特尼筛法（高效算法）
     * 输出1~n的所有素数
     */
    public static void printPrimesBySieve(int n) {
        long startTime = System.currentTimeMillis();

        // 创建标记数组，初始都标记为素数
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 筛法核心：从2开始，标记倍数
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                // 标记i的所有倍数为非素数
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 输出素数，每行5个
        int count = 0;
        int primeCount = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.printf("%-6d", i);  // 格式化输出，每个数占6位
                primeCount++;
                count++;

                // 每输出5个换行
                if (count % 5 == 0) {
                    System.out.println();
                }
            }
        }

        // 如果最后一行不满5个，也换行
        if (count % 5 != 0) {
            System.out.println();
        }

        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;

        System.out.println("\n=== 性能分析 ===");
        System.out.println("1~" + n + "范围内的素数个数: " + primeCount);
        System.out.println("筛法执行时间: " + duration + " 毫秒");

        // 性能对比：测试基础方法
        testBasicMethodPerformance(n);
    }

    /**
     * 测试基础方法的性能用于对比
     */
    public static void testBasicMethodPerformance(int n) {
        long startTime = System.currentTimeMillis();
        int primeCount = 0;

        for (int i = 2; i <= n; i++) {
            if (isPrimeBasic(i)) {
                primeCount++;
            }
        }

        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;

        System.out.println("基础方法执行时间: " + duration + " 毫秒");
        System.out.println("筛法比基础方法快: " + (duration - (endTime - startTime)) + " 毫秒");
    }

    /**
     * 性能分析报告
     */
    public static void generatePerformanceReport() {
        System.out.println("\n=== 性能分析报告 ===");
        System.out.println("1. 最费时的函数: isPrimeBasic() 基础判断法");
        System.out.println("2. 性能瓶颈分析:");
        System.out.println("   - 基础方法对每个数单独判断，重复计算");
        System.out.println("   - 时间复杂度: O(n√n)");
        System.out.println("   - 筛法时间复杂度: O(n log log n)");
        System.out.println("3. 优化方案:");
        System.out.println("   - 使用筛法避免重复判断");
        System.out.println("   - 只标记奇数，减少内存占用");
        System.out.println("   - 使用位运算进一步优化");
    }

    public static void main(String[] args) {
        int limit = 20000;

        System.out.println("=== 输出1~" + limit + "的素数（每行5个）===");
        printPrimesBySieve(limit);

        generatePerformanceReport();

        // 额外测试：比较不同范围的性能
        System.out.println("\n=== 不同范围的性能对比 ===");
        testDifferentRanges();
    }

    /**
     * 测试不同范围的性能
     */
    public static void testDifferentRanges() {
        int[] testRanges = {1000, 5000, 10000, 20000};

        for (int range : testRanges) {
            long startTime = System.currentTimeMillis();

            boolean[] isPrime = new boolean[range + 1];
            for (int i = 2; i <= range; i++) isPrime[i] = true;

            for (int i = 2; i * i <= range; i++) {
                if (isPrime[i]) {
                    for (int j = i * i; j <= range; j += i) {
                        isPrime[j] = false;
                    }
                }
            }

            int count = 0;
            for (int i = 2; i <= range; i++) {
                if (isPrime[i]) count++;
            }

            long endTime = System.currentTimeMillis();
            System.out.println("范围 1~" + range + ": " + count + "个素数, 时间: " + (endTime - startTime) + "ms");
        }
    }
}